package linkLIstTest;

import org.w3c.dom.ls.LSOutput;

public class Link {
    static class ListNode{
        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return  val + "";
        }
    }
    //定义链表的头结点
    ListNode head;
    public void createList(){
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
    }
    /*
    * cur == null 表示将链表所有数据遍历完成
    * cur.next == null 表示cur现在指向链表最后一个元素
    * */
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = head;
        if(cur == null){
            head = node;
            return;
        }
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
    //任意位置插入
    public void addIndex(int index,int data){
        ListNode node = new ListNode(data);
        if(index < 0 || index >size()){
            throw new ExceptionIndexOutOfBounds("index 下标异常");
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndexSubOne(index);
        node.next = cur.next;
        cur.next = node;
    }
    /*
    * 找到当前节点的前一个元素
    * 定义cur走index-1步
    * */
    private ListNode findIndexSubOne(int index){
        ListNode cur = head;
        index -= 1;
        while(index-- != 0){
            cur = cur.next;
        }
        return cur;
    }
    //查看关键字key是否在单链表中
    public  boolean contains(int key){
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字key的节点
    /*
    * 找到删除节点的前一个节点
    * cur.next = cur.next.next  即可删除
    * */
    public void remove(int key){
        ListNode cur = searchPrev(key);
        if(head == null){
            return;
        }
        //单独删除头结点，因为头结点没有前驱节点
        if(head.val ==key){
            head = head.next;
            return;
        }
        if(cur == null){
            System.out.println("没有你要删除的值");
        }
        cur.next = cur.next.next;
    }
    /*
    * 找到当前要删除值的前驱
    * */
    private ListNode searchPrev(int key){
        ListNode cur = head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head == null){
            return;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else{
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key){
            head = head.next;
        }
    }
    //返回单链表的长度
    public int size(){
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    public void clear(){
        head = null;
    }
    public void display(){
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    //从任意位置打印链表
    public static void display(ListNode newHead){
        ListNode cur = newHead;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }


    /*
    * 一下为一些基本题型
    * */

    //翻转链表
    public  void reverseList(){
        if(head == null) return;
        if(head.next == null) return;
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
    }
    //输出链表的中间节点
    public ListNode medieuIndex(){
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next !=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    //输出倒数第k个节点
    public ListNode reciprocal(int k){
        if(k <= 0 || head ==null)  return null;
        ListNode slow = head;
        ListNode fast = head;
        while(k-- > 0){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    //合并两个有序列表为一个新的有序列表
    public static ListNode merge(Link A,Link B) {
        ListNode headA = A.head;
        ListNode headB = B.head;
        ListNode newHead = new ListNode(0);
        ListNode cur = newHead;
        while (headA != null && headB != null) {
            if (headA.val <= headB.val) {
                cur.next = headA;
                headA = headA.next;
            } else {
                cur.next = headB;
                headB = headB.next;
            }
            cur = cur.next;
        }
        if (headA != null) {
            cur.next = headA;
        }
        if (headB != null) {
            cur.next = headB;
        }
        return newHead.next;
    }
    //以x为基准将链分为两部分，小于x的排在前，大于x的排在后
    public ListNode partition(int x){
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                //第一次插入
                if(bs == null){
                    bs = be= cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            }else {
                if(as == null){
                    as = ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //第一个段没有数据
        if(bs == null){
            return as;
        }
        be.next = as;
        //最后一个节点不是最大数,要将节点的next置为空，否则链表张会存在一个环
        if(ae.next != null){
            ae.next = null;
        }
        return bs;
    }

    //判断链表是否为回文结构
    public boolean isHui(){
        if(head == null){
            return false;
        }
        //先找到链表的中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //开始翻转
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curNext = cur.next;    //记录下一个节点
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //开始判断是否回文
        while(head != slow){
            if(head.val != slow.val){
                return false;
            }
            //链表为偶数，否则会判断出错
            if(head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    //输入两个链表求出他们的第一个公共节点
    public ListNode intersection(Link A,Link B){
        ListNode pL = A.head;
        ListNode pS = B.head;
        int lenA = 0;
        int lenB = 0;
        //求出两个链表的长度。确定最长的那个
        while(pL != null){
            lenA++;
            pL = pL.next;
        }
        while(pS != null){
            lenB++;
            pS = pS.next;
        }
        pL = A.head;
        pS = B.head;
        //求出两个链表差值,并进行修正,保证pL永远指向长链表
        int len = lenA - lenB;
        if(len < 0){
            pL = B.head;
            pS = A.head;
            len = lenB - lenA;
        }
        //令长链表先走差值步
        while(len-- > 0){
            pL = pL.next;
        }
        //两个链表再走到交点处
        while(pL != null && pS !=null){
            if(pL == pS) {
                return pL;
            }
            pL = pL.next;
            pS = pS.next;
        }
        return null;
    }

    //判断链表中是否有环
    public boolean exsitCycle(){
        if(head == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        //在该循环中，若链表中无环则循环可结束，如有环则返回true
        //不会存在死循环的情况
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

    //给定一个链表返回链表开始入环的第一个节点，若链表无环则返回NULL
    public ListNode firstIntersection(){
        if(head == null) return null;
        //判断链表是否有环
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        //说明链表无环
        if(fast == null || fast.next == null){
            return null;
        }
        //链表有环，此时找X=Y的情况
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
    //删除链表中连续重复的元素
    public ListNode deleteRepetion(){
        ListNode cur = head;
        ListNode newHead = new ListNode(-1);
        ListNode tmpHead = newHead;
        while(cur != null){
            if(cur.next != null && cur.val == cur.next.val){
                while(cur.next != null && cur.val == cur.next.val){
                    cur = cur.next;
                }
                //将链表从最后一个重复的节点移动向下一个
                cur = cur.next;
            } else {
                tmpHead.next = cur;
                tmpHead = tmpHead.next;
                cur = cur.next;
            }
            //为防止链表最后一个元素仍未空，但tmpHead的指针断掉，将tmpHead的指针手动置为空
            tmpHead.next = null;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        Link linkA = new Link();
        linkA.addFirst(500);
        linkA.addFirst(400);
        linkA.addFirst(300);
        linkA.addFirst(200);
        linkA.addFirst(100);
        Link linkB = new Link();
        linkB.addFirst(99);
        linkB.addFirst(66);
        linkB.addFirst(33);
        ListNode a= merge(linkA,linkB);
        display(a);
    }
}
